import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
    47. 全排列 II
    重点：模仿子集2的思路，在全排列1的基础上多加一个判断，
    如果前一个数没被选，并且和当前数相同，那么应直接跳过，
    因为之前的数一定有被选的情况，那么如果当前数也被选，那么一定会产生和之前一样的情况，
    还有就是，要先排序
 */

public class PermuteUnique {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        ArrayList<Integer> temp = new ArrayList<>();
        Arrays.sort(nums);
        process(nums, 0, temp, flag);
        return ans;
    }

    public void process(int[] nums, int i, List<Integer> list, boolean[] flag) {
        if (nums.length == i) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int j = 0; j < nums.length; j++) {
            if (flag[j] || (j > 0 && nums[j] == nums[j - 1] && !flag[j - 1])) {
                continue;
            }
            flag[j] = true;
            list.add(nums[j]);
            process(nums, i + 1, list, flag);
            list.remove(list.size() - 1);
            flag[j] = false;
        }
    }
}
